type 'a binary_tree =
  | Empty
  | Node of 'a * 'a binary_tree * 'a binary_tree   (* 当前节点 ，当前左子树，当前右子树 *)
;;

let example_layout_tree =
  let leaf x = Node (x, Empty, Empty) in
  Node ('n', Node ('k', Node ('c', leaf 'a',
                           Node ('e', leaf 'd', leaf 'g')),
                 leaf 'm'),
       Node ('u', Node ('p', Empty, leaf 'q'), Empty))
;;

(* 通过检测最左路径的“缺失深度”，动态调整整棵树的 x 起始位置，
   使得最左的叶节点尽可能靠近 x=1，节省水平空间，避免布局过于靠右 
   先计算树高 h,每层间距 = 2^h−depth−1, 根理想位置 = 2^h−1
   但根据最左路径缺失层数，向左平移 translate_dst = 2^missing - 1 *)
let layout_binary_tree_2 t =
  let rec height = function
    | Empty -> 0
    | Node (_, l, r) -> 1 + max (height l) (height r) in
  let tree_height = height t in
  (* find_missing_left 计算从根到最左路径上的层数
     目的：确定最左侧是否“短”，从而决定整体布局是否需要向右平移，避免最左节点被画到负坐标。*) 
  let rec find_missing_left depth = function
    | Empty -> tree_height - depth
    | Node (_, l, _) -> find_missing_left (depth + 1) l in
  (* translate_dst 计算平移量, 1 lsl n 是位运算，等于 2^n 
    作用：这是一个水平偏移量，用于将整棵树向右移动，确保最左边的节点不会出现在 x < 1 的位置 *)
  let translate_dst = 1 lsl (find_missing_left 0 t) - 1 in
  let rec layout depth x_root = function
    | Empty -> Empty
    | Node (x, l, r) ->
    (*spacing：当前层子节点之间的水平间距*)
       let spacing = 1 lsl (tree_height - depth - 1) in
       let l' = layout (depth + 1) (x_root - spacing) l
       and r' = layout (depth + 1) (x_root + spacing) r in
         Node((x, x_root, depth), l',r') in
  layout 1 ((1 lsl (tree_height - 1)) - translate_dst) t
;;

layout_binary_tree_2 example_layout_tree ;;